package gold.gold04;

import java.util.Arrays;

/**
 *
 * 背包问题, 背包九讲要看一下, 没写出来
 */
public class S0811硬币_几种金额凑成别的金额 {
    /**
     * 91, 累了, 看了背包九讲才会写。
     * 怎么看着又不像背包问题, 这是求组合的数量
     * 太强了
     */
    public int waysToChange(int n) {
        int[] record = new int[n + 1];
        Arrays.fill(record, 1);
        int[] coins = new int[]{5, 10, 25};
        for(int coin : coins){
            for(int i = coin, tempBound1 = n + 1; i < tempBound1; i++){
                record[i] = (record[i] + record[i - coin]) % 1000000007;
            }
        }
        return record[n];
    }

    /**
     * 这个不用初始化。用long先存着也是个办法
     */
    static final int MOD = 1000000007;
    int[] coins = {25, 10, 5, 1};

    public int waysToChange2(int n) {
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int c = 0; c < 4; ++c) {
            int coin = coins[c];
            for (int i = coin; i <= n; ++i) {
                f[i] = (f[i] + f[i - coin]) % MOD;
            }
        }
        return f[n];
    }

    // 数学法不好想。
    public int waysToChange3(int n) {
        int ans = 0;
        for (int i = 0; i * 25 <= n; ++i) {
            int rest = n - i * 25;
            int a = rest / 10;
            int b = rest % 10 / 5;
            ans = (ans + (int) ((long) (a + 1) * (a + b + 1) % MOD)) % MOD;
        }
        return ans;
    }


}
